정보과학회 논문지 C : 컴퓨팅의 실제
Current Result Document :
| 한글제목(Korean Title) |
멀티코어 환경에서의 접미사 트리 병렬 생성 알고리즘 |
| 영문제목(English Title) |
Parallel Construction of Suffix Trees on Multi-core Platforms |
| 저자(Author) |
서준호
나중채
JunHo Seo
JoongChae Na
|
| 원문수록처(Citation) |
VOL 18 NO. 11 PP. 0799 ~ 0803 (2012. 11) |
한글내용
(Korean Abstract) |
접미사 트리는 문자열 압축, 텍스트 처리, 생물정보학 등 다양한 응용 분야에서 사용되는 자료구조이다. 최근 분산 시스템, 멀티코어 CPU 등 병렬처리 시스템이 보급됨에 따라 접미사 트리를 병렬로 생성하는 알고리즘의 구현에 대한 연구가 활발히 진행되고 있다. 본 논문에서는 Threading Building Blocks(TBB)와 Cilk Plus 병렬 라이브러리를 이용하여 멀티코어 환경에서 동작하는 병렬 접미사 트리 생성 알고리즘을 실제로 구현한다. 본 논문의 구현은 분산시스템에서 구현된 Chen과 Schmidt의 알고리즘을 기반으로 한다. 또한 다양한 종류의 입력 문자열에 대한 실험을 통하여 구현된 알고리즘의 성능을 비교 분석한다.
|
영문내용
(English Abstract) |
The suffix tree is a data structure used in a wide range of domains such as data compression, text processing, computational biology, and so on. Recently, as parallel architectures such as distributed systems and multi-core CPUs have been developed, there has been studies on implementing the parallel construction of the suffix tree. In this paper, we implement a parallel suffix tree construction algorithm on multi-core platforms using parallel libraries, Threading Building Blocks (TBB) and Cilk Plus. Our implementation is based on Chen and Schmidt’s algorithm proposed for distributed systems. Furthermore, through experiments with various kinds of input strings, we measure and analyze the performance of the parallel algorithms
|
| 키워드(Keyword) |
접미사트리
병렬알고리즘
Suffix Tree
Parallel Algorithm
TBB
Cilk Plus
|
| 파일첨부 |
PDF 다운로드
|
